﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithm.Easy_20_ValidArentheses
{
    class MainProject
    {
        //有效的括号
        //未完成
        static void Main(string[] args)
        {
            string s = "[[(){{}[{}]([])}{}{{}}]{}]";

            Console.WriteLine(IsValid(s));
            Console.ReadKey();
        }

        public static void Recursion(int index, string s, Dictionary<char, char> findValue)
        {
            if (index>= s.Length)
            {
                return;
            }
            char ch = s[index];
            if (findValue.ContainsKey(ch))
            {
                int othetIndex = s.IndexOf(findValue[ch]);
                if (true)
                {

                }
            }
        }

        public static bool IsValid(string s)
        {
           if (s == "" || s == null) return false;

            // 反着的原因是，进入栈的值必须为左边括号，这样可以判断出栈的值与当前dic的值是否相等 真巧妙
            Dictionary<char, char> dic = new Dictionary<char, char> { { ']', '[' }, { ')', '(' }, { '}', '{' } };

            var stack = new Stack<char>();
            foreach (var c in s)
            {
                if (dic.ContainsKey(c))
                {
                    // 栈为空时说明第一个字符为右括号
                    if (stack.Count == 0) return false;
                    // 出栈的值与当前dic的值不相等就返回 false
                    if (stack.Pop() != dic[c]) return false;
                }
                else
                    stack.Push(c);
            }

            return stack.Count == 0 ? true : false;
        }
    }
}
